1433D - Districts Connection - CodeForces Solution


constructive algorithms dfs and similar *1200

Please click on ads to support us..

Python Code:

I=lambda: map(int, input().split())
for _ in [0]*int(input()):
    n=int(input())
    a=list(I())
    c=list(set(a))
    if len(set(a))==1:
        print('NO')
    else:
        x=c[0]
        y=c[1]
        indx=a.index(x)+1
        indy=a.index(y)+1
        print('YES')
        print(indx,indy)
        i=1
        for v in a:
            if i!=indx and i!=indy:
                if v!=x:
                    print(indx,i)
                else:
                    print(indy,i)
            i=i+1

C++ Code:

#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
using LL = long long;
const int mod = 1e9+7;
const int M = 500000;
template<class T>
inline void out(T s )
{
	cout<<s<<endl;
}
inline void out(bool f)
{
	if(f)cout<<"YES\n";
	else cout<<"NO\n";
}
template<typename T>
T Max(T &&a,T &&b)
{
	return a>b?a:b;
}
template<typename T,typename... Args>
T Max(T &&a, Args... arg)
{
	T tmp= Max(arg...); 
	return Max(a,tmp);
}

int dis(int x,int y,int n,int m)
{
	return abs(x-n)+abs(y-m);
}
void fun(int x,int y, int p)
{
	
}
void ots(string s)
{
	bool flag = 1;
	for(int i=0;i<s.length();i++)
	{
		if(flag && s[i] == '0')continue;
		cout<<s[i];
		flag = 0;
	}
	if(flag)cout<<"0";
}
const LL INF  = 0x3f3f3f3f;
int pre[M];
int fin(int x)
{
	return x==pre[x]? x :pre[x] = fin(pre[x]);
}
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)pre[i] = i;
	vector<int>a(n+1);
	vector<pair<int,int>>ans;
	a[0] = INF;
	int num = 0;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(num == n-1)break;
			if(a[i] != a[j])
			{
				int x =fin(i),y = fin(j);
				if(x!=y)
				{
					pre[x] = y;
					num++;
					ans.push_back({i,j});
				}
			}
		}
	out( num == n-1);
	if(num == n-1)
	for(auto c:ans)
	cout<<c.first<<" "<<c.second<<endl;
}
int main()
{
	int tt = 1;
	cin >> tt;
	while(tt--)
	solve();
	return 0;
}
	 	  		   				 	 	   					  	 	


Comments

Submit
0 Comments
More Questions

574A - Bear and Elections
352B - Jeff and Periods
1244A - Pens and Pencils
1670A - Prof Slim
1189A - Keanu Reeves
678A - Johny Likes Numbers
1699C - The Third Problem
1697D - Guess The String
754B - Ilya and tic-tac-toe game
760A - Petr and a calendar
1573A - Countdown
166A - Rank List
1631B - Fun with Even Subarrays
727A - Transformation from A to B
822B - Crossword solving
1623A - Robot Cleaner
884B - Japanese Crosswords Strike Back
862B - Mahmoud and Ehab and the bipartiteness
429A - Xor-tree
1675C - Detective Task
950A - Left-handers Right-handers and Ambidexters
672B - Different is Good
1C - Ancient Berland Circus
721A - One-dimensional Japanese Crossword
1715B - Beautiful Array
60B - Serial Time
453A - Little Pony and Expected Maximum
1715A - Crossmarket
1715C - Monoblock
1512C - A-B Palindrome